package com.linyaonan.leetcode.medium._1461;

import java.util.ArrayList;

/**
 *
 * 给你一个二进制字符串 s 和一个整数 k 。如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 true ，否则请返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "00110110", k = 2
 * 输出：true
 * 解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。
 * 示例 2：
 *
 * 输入：s = "0110", k = 1
 * 输出：true
 * 解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。
 * 示例 3：
 *
 * 输入：s = "0110", k = 2
 * 输出：false
 * 解释：长度为 2 的二进制串 "00" 没有出现在 s 中。
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 5 * 105
 * s[i] 不是'0' 就是 '1'
 * 1 <= k <= 20
 *
 * @author: Lin
 * @date: 2024/10/26
 */
public class CheckIfAStringContainsAllBinary {

    public boolean hasAllCodes(String s, int k) {
        int ww = (1 << (k - 1)) - 1;
        // 1. 申请如此长度的数组长度用来存放出现的数值
        int rang = getRang(k);
        // 00110110
        boolean[] save = new boolean[rang];
        int add = 0;
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            count++;
            add = rightAdd(add, (s.charAt(i) == '0'));
            if (count < k) {
                continue;
            }
            save[add] = true;
            add = removeFirst(add, ww);
            count--;
        }

        for (boolean b : save) {
            if (!b) {
                return false;
            }
        }

        return true;

    }

    /**
     * 通过k长度可以确定组成的数值范围
     * 例如 k = 2 那么最大的数值为 0 ~（二进制）100 - 1
     * k = 4 那么组成最大的数值为 0 ~（二进制）10000 - 1
     * 1048575
     * @param k
     * @return
     */
    public int getRang(int k) {
        return 1 << k;
    }

    public int rightAdd(int pre, boolean isZero) {
        return (pre << 1) + (isZero ? 0 : 1);
    }

    public int removeFirst(int pre, int ww) {
        return (pre & ww);
    }

}
